This invention was made with Government support under Contract; No. N00140-86-C-8996 awarded by the Defense Advanced Research Projects Agency (DARPA). The Government has certain rights in this invention.
The present invention relates to techniques for image processing. More specifically, the invention relates to editing an image of text defined by digital data. For example, the image can be defined by a two-dimensional data array.
Kim, S. E., Viewpoint: Toward a Computer for Visual Thinkers, University Microfilms, Ann Arbor, 1988, pp. 22-97, 115, and 123-131 describes Viewpoint, a text and graphics editor. Pages 22-23 describe pixels, indicating that every structure in Viewpoint can be edited as pixels. Pages 24-25 describe Viewpoint, indicating that the representative form of structured graphics in Viewpoint is text, which uses a single, fixed width font, positioned on a fixed grid of square cells to simplify character parsing; text and graphics editing both work on cells. Pages 29-81 describe a demonstration of Viewpoint, with illustrations: Page 36 shows the effect of selecting a cell, including a large scale reproduction in a special screen area; pages 38-39 illustrate copying; pages 42-57 describe typing, including word wrap on encountering a noncharacter, deletion, font editing, and overtyping; pages 58-69 describe a visual boot, showing how the keyboard is built up; pages 70-81 describe edges of the system, including typing off the edge of the screen and drawing over a key border or a key image. Pages 84-97 describe inner workings of Viewpoint, with page 85 indicating that text is treated as a kind of graphics, page 93 describing how word wrap reveals the structure of text by pixel parsing to find the ends of lines and word breaks. Page 115 describes text editors, indicating that another editor stores text as a rectangular array of character cells and scans patterns of spaces and characters to locate paragraph and column breaks. Pages 123-125 are a Viewpoint manual, explaining at item 9 how typing a key copies the contents of the appropriate key image cell to the current cell, advancing the cursor one cell.
Suenaga, Y., and Nagura, M., "A Facsimile Based Manuscript Layout and Editing System by Auxiliary Mark Recognition," 5th International Conference on Pattern Recognition Proceedings, Dec. 1-4, 1980, Vol. 2, pp. 856-858, describe an editor whose only input device is a FAX transmitter and whose only output device is a FAX receiver. FIG. 1 shows components of the system, including OCR, and FIG. 2 shows the processing flow, which includes a text editing subsystem and a graphics editing subsystem. The text editing subsystem, described on page 857, employs eleven handwritten auxiliary marks, shown in FIG. 3, which are input on separate paper from the text being edited. In response to an auxiliary mark, the text editing subsystem rearranges the binary picture of the text, as illustrated in FIGS. 4(a) and 4(b). The text format is estimated from the text picture. Marginal distribution (profile) and horizontal connectivity are used to divide the text picture into Segmented Blocks (SBs), corresponding to the rectangular regions which cover the individual characters in Japanese texts, individual words in alphanumeric texts, or graphics to be processed as binary patterns. A Segmented Block List (SBL) is constructed and used to extract and classify marks based on topological and metric features. A Mark Parameters List for Texts (MPL-T) is constructed. A Picture Allocation List (PAL), a list consisting of the SB numbers and their linkage addresses, is generated according to the MPL-T and SBL. Character strings or patterns are virtually deleted, moved, copied, and combined in PAL. The binary picture of the original text is rearranged according to the PAL to construct the fair copy.
Previous work is described in Suenaga, Y., "A Facsimile Based Text Editor Using Handwritten Mark Recognition," Proceedings of the Sixth International Joint Conference on Artificial Intelligence, Tokyo, Aug. 20-23, 1979, Vol. 2, 1979, pp. 856-858. Page 856 indicates that the method can be combined with usual text editors or word processors. Page 856 also states the assumption that characters must be placed according to ruled lines and describes the position mark drawn according to the ruled lines and from which the format and block size of manuscripts are estimated. Page 857 describes the picture allocation list (PAL) as consisting of block numbers and addresses indicating the order.
Wong, K. Y., Casey, R. G., and Wahl, F. M., "Document Analysis System," IBM Journal of Research and Development, Vol. 26, No. 6, November 1982, pp. 647-656, describe a system, shown in FIG. 1, that assists a user in encoding printed documents for computer processing. An Image Manipulation Editor (IEDIT) described at pages 648-649 reads and stores images on disk and provides image-editing functions such as copy, move, erase, etc. As described at pages 649-656, a digitized printed document is segmented and classified into regions of text and images. Blocks containing text can be analyzed with a pattern-matching program that groups similar symbols from the document and creates a prototype pattern to represent each group. During pattern matching, the position and matching prototype index for each text pattern is recorded; the position may be the coordinates of the lower left corner of the array representing the pattern. The prototype patterns are identified interactively or by automatic recognition logic.